package common;

/**
 * 并查集
 * 一定要记住，并查集查的是集合的代表数字
 */
public class UnionFind {

    public int MAX = 100000;
    public int[] father;
    public int sets;

    public UnionFind(int n) {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        sets = n;
    }

    /**
     * i表示当前节点，
     * father[i]表示代表节点
     * 代表节点 i == father[i]
     */
    public int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    public boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
            sets--;
        }
    }
}
